package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 113. 路径总和 II
 * 深度优先搜索 Solution113_3 更简单的写法
 *
 * @author fy
 * @date 2022/4/24 21:22
 */
public class Solution113_3_1 {

    private List<List<Integer>> res = new ArrayList<>();
    private Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }

    private void dfs(TreeNode node, int targetSum) {
        if (node == null) {
            return;
        }
        targetSum -= node.val;
        path.offerLast(node.val);
        // 这里不写return的话会多调用一次dfs, 但是node为null会直接返回, 代码更简洁
        if (node.left == null && node.right == null && targetSum == 0) {
            res.add(new ArrayList<>(path));
        }
        dfs(node.left, targetSum);
        dfs(node.right, targetSum);
        path.pollLast();
    }

}
